#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>

#include "typedef.h"


#define MATCH_SAFEGUARD_DISTANCE  12
#define LASTLITERALS   5 
#define WILDCOPYLENGTH 8
#define FASTLOOP_SAFE_DISTANCE 64
#define MINMATCH 4
#define MFLIMIT  12 
#define ML_MASK  15
#define RUN_MASK 15


#pragma pack(1)
typedef union 
{ 
	U16 u16; 
	U32 u32; 
} unalign;
#pragma pack()


unsigned int inc32table[8] = {0, 1, 2,  1,  0,  4, 4, 4};
int dec64table[8] = {0, 0, 0, -1, -4,  1, 2, 3};


U16 LZ4_readLE16(void* memPtr)
{
	return ((unalign*)memPtr)->u16; 
}

void LZ4_write32(void* memPtr, U32 value) 
{ 
	((unalign*)memPtr)->u32 = value; 
}

unsigned read_variable_length(U8 **ip, U8* lencheck, int loop_check, int initial_check, int* error)
{
    U32 s, length = 0;
    
    if (initial_check && (*ip) >= lencheck) {
        *error = -1;
        return length;
    }
    do {
        s = **ip;
        (*ip)++;
        length += s;
        if (loop_check && (*ip) >= lencheck) {  
            *error = -2;
            return length;
        }
    } while (s == 255);

    return length;
}

void LZ4_wildCopy8(void* dstPtr, void* srcPtr, void* dstEnd)
{
    U8* d = (U8*)dstPtr;
    U8* s = (U8*)srcPtr;
    U8* e = (U8*)dstEnd;

    do { 
    	memcpy(d,s,8); 
    	d+=8; 
    	s+=8; 
	} while (d<e);
}

void LZ4_wildCopy32(void* dstPtr, void* srcPtr, void* dstEnd)
{
    U8* d = (U8*)dstPtr;
    U8* s = (U8*)srcPtr;
    U8* e = (U8*)dstEnd;

    do { 
     	memcpy(d,s,16); 
     	memcpy(d+16,s+16,16); 
     	d+=32; 
     	s+=32; 
 	} while (d<e);
}

void LZ4_memcpy_using_offset_base(U8* dstPtr, U8* srcPtr, U8* dstEnd, U32 offset)
{
    assert(srcPtr + offset == dstPtr);
    if (offset < 8) {
        LZ4_write32(dstPtr, 0);   
        dstPtr[0] = srcPtr[0];
        dstPtr[1] = srcPtr[1];
        dstPtr[2] = srcPtr[2];
        dstPtr[3] = srcPtr[3];
        srcPtr += inc32table[offset];
        memcpy(dstPtr+4, srcPtr, 4);
        srcPtr -= dec64table[offset];
        dstPtr += 8;
    } else {
        memcpy(dstPtr, srcPtr, 8);
        dstPtr += 8;
        srcPtr += 8;
    }

    LZ4_wildCopy8(dstPtr, srcPtr, dstEnd);
}

void LZ4_memcpy_using_offset(U8* dstPtr, U8* srcPtr, U8* dstEnd, U32 offset)
{
    U8 v[8];

    assert(dstEnd >= dstPtr + MINMATCH);

    switch(offset) {
    case 1:
        memset(v, *srcPtr, 8);
        break;
    case 2:
        memcpy(v, srcPtr, 2);
        memcpy(&v[2], srcPtr, 2);
        memcpy(&v[4], v, 4);
        break;
    case 4:
        memcpy(v, srcPtr, 4);
        memcpy(&v[4], srcPtr, 4);
        break;
    default:
        LZ4_memcpy_using_offset_base(dstPtr, srcPtr, dstEnd, offset);
        return;
    }

    memcpy(dstPtr, v, 8);
    dstPtr += 8;
    while (dstPtr < dstEnd) {
        memcpy(dstPtr, v, 8);
        dstPtr += 8;
    }
}

int lz4_decompress(U8 *src, U8 *dst, int srcSize, int outputSize)
{
    U8* ip = src;
    U8* iend = src + srcSize;
    U8* op = dst;
    U8* oend = dst + outputSize;
    U8* cpy;

    U8* shortiend = iend - 16;
    U8* shortoend = oend - 32;

    U8* match;
    U32 offset;
    U32 token;
    U32 length;

    while (1) {
        assert(oend - op >= FASTLOOP_SAFE_DISTANCE);
        assert(ip < iend);
        
        token = *ip++;
        length = token >> 4;  

        assert(ip <= iend);

        if (length == RUN_MASK) {
            int error = 0;
            length += read_variable_length(&ip, iend-RUN_MASK, 1, 1, &error);
            if (error == -1) { goto _output_error; }

            cpy = op+length;
            if ((cpy>oend-32) || (ip+length>iend-32)) { goto safe_literal_copy; }
            LZ4_wildCopy32(op, ip, cpy);
            ip += length; op = cpy;
        } else {
            cpy = op+length;
            if (ip > iend-17) { goto safe_literal_copy; }
            memcpy(op, ip, 16);
            ip += length; op = cpy;
        }

        offset = LZ4_readLE16(ip); ip+=2;
        match = op - offset;
        assert(match <= op);

        length = token & ML_MASK;

        if (length == ML_MASK) {
            int error = 0;
            if ((match + 0 < dst)) { goto _output_error; }
            length += read_variable_length(&ip, iend - LASTLITERALS + 1, 1, 0, &error);
            if (error != 0) { goto _output_error; }
            length += MINMATCH;
            if (op + length >= oend - FASTLOOP_SAFE_DISTANCE) {
                goto safe_match_copy;
            }
        } else {
            length += MINMATCH;
            if (op + length >= oend - FASTLOOP_SAFE_DISTANCE) {
                goto safe_match_copy;
            }

            if (match >= dst) {
                if (offset >= 8) {
                    assert(match >= dst);
                    assert(match <= op);
                    assert(op + 18 <= oend);

                    memcpy(op, match, 8);
                    memcpy(op+8, match+8, 8);
                    memcpy(op+16, match+16, 2);
                    op += length;
                    continue;
        }   }   }

        if (1 && (match < dst)) { goto _output_error; } 

        cpy = op + length;

        assert((op <= oend) && (oend-op >= 32));
        if (offset<16) {
            LZ4_memcpy_using_offset(op, match, cpy, offset);
        } else {
            LZ4_wildCopy32(op, match, cpy);
        }

        op = cpy;   
    }

    while (1) {
        token = *ip++;
        length = token >> 4;  

        assert(ip <= iend); 

        if ( (length != RUN_MASK) && (ip < shortiend) & (op <= shortoend) ) {
            memcpy(op, ip, 16);
            op += length; 
            ip += length;

            length = token & ML_MASK; 
            offset = LZ4_readLE16(ip); 
            ip += 2;
            match = op - offset;
            assert(match <= op);

            if ( (length != ML_MASK)
              && (offset >= 8)
              && (match >= dst) ) {
                memcpy(op + 0, match + 0, 8);
                memcpy(op + 8, match + 8, 8);
                memcpy(op +16, match +16, 2);
                op += length + MINMATCH;
                continue;
            }

            goto _copy_match;
        }

        if (length == RUN_MASK) {
            int error = 0;
            length += read_variable_length(&ip, iend-RUN_MASK, 1, 1, &error);
            if (error == -1) { goto _output_error; }
        }

        cpy = op+length;
safe_literal_copy:
        if ( (((cpy>oend-MFLIMIT) || (ip+length>iend-(3+LASTLITERALS))) ) )
        {
            if (((ip+length != iend) || (cpy > oend))) {
                goto _output_error;
            }
            memmove(op, ip, length); 
            ip += length;
            op += length;
            break;
        } else {
            LZ4_wildCopy8(op, ip, cpy);  
            ip += length; op = cpy;
        }

        offset = LZ4_readLE16(ip); ip+=2;
        match = op - offset;

        length = token & ML_MASK;

_copy_match:
        if (length == ML_MASK) {
          int error = 0;
          length += read_variable_length(&ip, iend - LASTLITERALS + 1, 1, 0, &error);
          if (error != 0) goto _output_error;
        }
        length += MINMATCH;

safe_match_copy:
        if ((match + 0 < dst)) goto _output_error;  
        assert(match >= dst);

        cpy = op + length;

        assert(op<=oend);

        if (offset<8) {
            LZ4_write32(op, 0);   
            op[0] = match[0];
            op[1] = match[1];
            op[2] = match[2];
            op[3] = match[3];
            match += inc32table[offset];
            memcpy(op+4, match, 4);
            match -= dec64table[offset];
        } else {
            memcpy(op, match, 8);
            match += 8;
        }
        op += 8;

        if (cpy > oend-MATCH_SAFEGUARD_DISTANCE) {
            U8* oCopyLimit = oend - (WILDCOPYLENGTH-1);
            if (cpy > oend-LASTLITERALS) { goto _output_error; } 
            if (op < oCopyLimit) {
                LZ4_wildCopy8(op, match, oCopyLimit);
                match += oCopyLimit - op;
                op = oCopyLimit;
            }
            while (op < cpy) { *op++ = *match++; }
        } else {
            memcpy(op, match, 8);
            if (length > 16)  { LZ4_wildCopy8(op+8, match+8, cpy); }
        }
        op = cpy;  
    }

   return (int)(op-dst);  

_output_error:
    return (int)(src-ip-1);
}

